#include <iostream>
#include <vector>
using namespace std;

// N 叉树节点的定义
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

// N 叉树的先根遍历
void preorder(Node* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";
    for (Node* child : root->children) {
        preorder(child);
    }
}

int main() {
    // 构造一个 N 叉树
    Node* node5 = new Node(5);
    Node* node6 = new Node(6);
    Node* node3 = new Node(3, {node5, node6});
    Node* node2 = new Node(2);
    Node* node4 = new Node(4);
    Node* root = new Node(1, {node3, node2, node4});

    // 执行先根遍历
    cout << "Preorder Traversal of the N-ary Tree: ";
    preorder(root);
    cout << endl;

    return 0;
}
